//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 子数组 是数组中的一个连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：nums = [5,4,-1,7,8]
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -10⁴ <= nums[i] <= 10⁴ 
// 
//
// 
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。 
//
// Related Topics 数组 分治 动态规划 👍 7114 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxSubArray(int[] nums) {
//        int maxSum = nums[0];
//        //穷举遍历
//        for(int i=0; i<nums.length; i++){
//            int sum = nums[i];
//            for(int j = i+1; j<nums.length; j++){
//                //求累积和。
//                sum += nums[j];
//                maxSum = Math.max(maxSum, sum);
//                //额外判断某个大数
//                maxSum = Math.max(maxSum, nums[j]);
//            }
//        }
//        return maxSum;
////        Time Limit Exceeded
//        //2.copy
//        int maxNum = nums[0];
//        for(int i = 0; i<nums.length; i++){
//            int zNum = nums[i];
//            for(int j=i+1; j<nums.length;j++){
//                zNum += nums[j];
//                if(zNum > maxNum)
//                    maxNum = zNum;
//                if(nums[j] > maxNum)
//                    maxNum = nums[j];
//            }
//        }
//        return maxNum;
////        Time Limit Exceeded
//        这个算法叫做 Kadane 算法（卡丹算法）。
//        Kadane 算法是一种用于求解 "最大子数组和" 问题的经典算法，由计算机科学家 Jay Kadane 提出。它的核心思想是通过动态规划的方式，在遍历数组的过程中不断决策：对于当前元素，是将其加入之前的子数组，还是以它为起点重新开始一个子数组。
        int currentMax = nums[0];
        int globalMax = nums[0];
        for(int i=1; i< nums.length; i++){
            currentMax = Math.max(nums[i], currentMax+nums[i]);
            if(currentMax>globalMax)
                globalMax = currentMax;
        }
        return globalMax;


    }
}
//leetcode submit region end(Prohibit modification and deletion)
